package com.liang.leetcode.array;

/**
 * 27：移除元素 -- 双指针
 * 给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。
 * 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。
 * 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素
 */
public class Array02_RemoveElement {
    public static void main(String[] args) {
        // int[] nums = {10, 11, 10, 13, 14, 10, 10, 17, 19, 10, 9};
        // int val = 10;
        int[] nums = {0, 1, 2, 2, 3, 0, 4, 2};
        int val = 2;
        int len = removeElement(nums, val);
        System.out.println(len);
        for (int i = 0; i < len; i++) {
            System.out.print(nums[i] + " ");
        }
    }
    
    /**
     * 解法一：暴力解法
     * 两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组
     * @param nums 数组
     * @param val  需要移除的数
     * @return 移除后数组的新长度
     */
    public static int removeElement(int[] nums, int val) {
        int len = nums.length;
        int i = 0;
        while (i < len) {
            // 发现需要移除的元素，就将数组集体向前移动一位
            if (nums[i] == val) {
                for (int j = i; j < nums.length - 1; j++) {
                    //后面的值移到前一个位置
                    nums[j] = nums[j + 1];
                }
                len--;
            } else {
                i++;
            }
        }
        return len;
    }

    /**
     * 解法二：双指针法，前方探路，后方整顿策略
     * 双指针法（快慢指针法）：通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。
     * 快指针：寻找新数组的元素，新数组就是不含有目标元素的数组，找到后赋值给慢指针的位置，慢指针索引加1
     * 慢指针：指向更新，新数组下标的位置
     * @param nums 原数组，其中包含可能需要移除的元素
     * @param val 指定的需要移除的元素值
     * @return nums=[1,3,5,3,7,8,3,9]
     */
    public static int removeElement1(int[] nums, int val) {
        int i = 0;
        for (int j = 0; j < nums.length; j++) {
            // j 指向不等于 val 的数组位置
            // 跳过需要移除的元素，即找到新数组所需要的元素
            if (nums[j] != val) {
                // 将不等于val的值移动到新数组的位置
                nums[i++] = nums[j];
            }
        }
        // 返回新数组的长度
        return i;
    }

    //双指针法：while循环写法
    public static int removeElement2(int[] nums, int val) {
        // 定义两个指针，一个慢指针用于标记非目标元素的位置，一个快指针用于遍历数组
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            //快数组找元素，并放入新数组中
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        //返回新数组长度
        return slow;
    }
    
    public static int removeElement4(int[] nums, int val) {
        int i = 0;
        int j = nums.length - 1;
        while (i < j) {
            while (nums[i] != val) {
                i++;
            }
            while (nums[j] == val) {
                j--;
            }
            nums[i] = nums[j--];
        }
        return i;
    }
}
